In messages to be sent there are often lists or groups of items of information that are compressed at the encoder and decompressed at the decoder. This is for example the case for HTTP (standing for Hypertext Transfer Protocol) where HTTP payload is compressed, as well as for SPDY protocol where HTTP headers are compressed.
SPDY is a protocol that intends to improve the well-known HTTP. The SPDY protocol is referred to below to illustrate the present invention, although the invention may apply to other configurations. In particular, it may apply to a large number of data transmission protocols where a list of information items is compressed, such as the above cited HTTP and SPDY protocols.
HTTP is commonly used to request and send web pages, and is based on a client/server architecture, wherein the client sends requests, namely HTTP requests, to the server, and the server replies to the client's requests with responses, namely HTTP responses.
Requests and responses are messages that comprise various parts, among which are non-compressed HTTP headers and compressed HTTP payload.
FIG. 1 represents an example of six HTTP headers that are successively listed in an HTTP request, and then in an HTTP response.
An HTTP header consists of a name (in bold in the Figure) along with a corresponding value.
For instance, in “Host: en.wikipedia.org”, Host is the header name, and its value is “en.wikipedia.org”. This header is used to indicate the host of the requested resource (for instance, the Wikipedia page describing HTTP, available at http://en.wikipedia.org/wiki/HTTP). HTTP headers are well-known to one skilled in the art, and therefore are not further detailed here.
In the first versions of HTTP, a TCP/IP connection was established for each HTTP request/response exchange.
SPDY is a protocol that improves HTTP in several ways.
First, it enables several HTTP requests and responses to be sent over a unique TCP/IP connection, thus defining a set of HTTP transmissions therein. In this way, all the components of a web page (HTML documents, images, JavaScript, etc.) may share the same TCP/IP connection, thus speeding up the web page loading.
Secondly, SPDY implements compression of the HTTP headers exchanged over the shared TCP/IP connection, using the Zlib Deflate algorithm (also known through the “zip” format). This binary compression reduces the network load.
The Deflate algorithm performs compression of a serialized binary representation of the HTTP headers, by searching (using a sliding window) and replacing duplicate strings of the binary representation with back references thereto, and replacing symbols of the back references with Huffman codes.
A serialized binary representation of the HTTP headers results from the serialization of the HTTP headers as a stream of bits (or bytes).
Compression gains obtained by SPDY are acceptable.
However, speed performance is observed to be poor, while memory consumption may become disadvantageously high.
The poor speed performance is due to the potentially large size of the serialized binary representation, resulting from a large number of headers.
High memory consumption may arise in the case of a HTTP server handling simultaneously a plurality of connections towards a plurality of clients. Independently encoding the headers of the messages transmitted over the different connections requires a large amount of memory, in particular when the number of connections increases: one encoder or compressor is assigned to each connection and a dedicated memory area is reserved for each encoder or compressor.
High memory consumption may arise relatively to constrained devices with low memory resources, for example on decoder side.
In this context, there is a need for a new approach for compressing a list of information items (such as HTTP headers) that achieves similar size reduction while substantially reducing the memory and processing costs. In embodiments, such new approach should be compatible with binary compression such as Deflate, in order to keep high compression performance.
The publication “A Proposal for Shared Dictionary Compression over HTTP” (J. Butler et al., 2008) discloses a shared dictionary used to encode cross-payload redundancy by substituting redundancy elements with references to the dictionary. However, the decoder cannot achieve a quick decoding of a large number of encoded elements, using a small amount of memory.
The present invention has been devised to address one or more of the foregoing concerns.